package com.dexter.year2023.charpter1_linkedlist.level2.topic2_1第一个公共结点;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

/**
 * 【寻找】两个链表的第一个公共结点
 * 来源：剑指offer 52. P253
 *
 * @author Dexter
 */
public class FindFirstCommonNode {
    public static void main(String[] args) {
        Node[] heads = initLinkedList();
        //la 为 1 2 3 4 5
        //lb 为 11 22 4 5
        Node la = heads[0];
        Node lb = heads[1];

        int testMethod = 5;
        // 结果
        Node res = new Node(Integer.MIN_VALUE);
        // 切换方法
        switch (testMethod) {
            case 1:
                // 法1：通过HashMap
                res = FindFirstCommonNodeByHashMap(la, lb);
                break;
            case 2:
                // 法2：通过HashSet
                res = FindFirstCommonNodeByHashSet(la, lb);
                break;
            case 3:
                // 法3：通过Stack
                res = FindFirstCommonNodeByStack(la, lb);
                break;
            case 4:
                // 法4：拼接两个链表
                res = FindFirstCommonNodeByCombine(la, lb);
                break;
            case 5:
                // 法5：求插值，快慢指针
                res = FindFirstCommonNodeBySub(la, lb);
                break;
            default:
                System.out.println("测试方法超出范围");
                break;
        }

        System.out.println("公共结点为：" + res.val);
    }

    /**
     * 创建结点
     */
    static class Node {
        public int val;
        public Node next;

        Node(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 构造输入链表
     *
     * @return
     */
    private static Node[] initLinkedList() {
        // 初始化两个链表A和B
        Node[] heads = new Node[2];
        // 构造A链表公共之前
        // 1
        heads[0] = new Node(1);
        Node headA = heads[0];
        // 1 -> 2
        headA.next = new Node(2);
        headA = headA.next;
        // 1 -> 2 -> 3
        headA.next = new Node(3);
        headA = headA.next;

        // 构造B链表公共之前
        // 11
        heads[1] = new Node(11);
        Node headB = heads[1];
        // 11 -> 22
        headB.next = new Node(22);
        headB = headB.next;

        // 构造两链表公共之后
        Node node4 = new Node(4);
        headA.next = node4;
        headB.next = node4;
        Node node5 = new Node(5);
        node4.next = node5;
        Node node6 = new Node(6);
        node4.next = node5;

        return heads;
    }

    /**
     * 法1：用HashMap
     *
     * @param headA
     * @param headB
     * @return
     */
    private static Node FindFirstCommonNodeByHashMap(Node headA, Node headB) {
        // 判空
        if (headA == null || headB == null) {
            return null;
        }
        // 初始化
        HashMap<Node, Object> hashMap = new HashMap<>();
        // 遍历A，加入hashMap
        while (headA != null) {
            hashMap.put(headA, null);
            headA = headA.next;
        }
        // 遍历B，去hashMap中对比
        while (headB != null) {
            if (hashMap.containsKey(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        // 找不到
        return null;
    }

    /**
     * 法2：用HashSet
     *
     * @param headA
     * @param headB
     * @return
     */
    private static Node FindFirstCommonNodeByHashSet(Node headA, Node headB) {
        // 判空
        if (headA == null || headB == null) {
            return null;
        }
        // 初始化
        HashSet<Node> set = new HashSet<>();
        // 遍历A，加入set
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        // 遍历B，去set中对比
        while (headB != null) {
            if (set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        // 找不到
        return null;
    }

    /**
     * 法3：用Stack
     *
     * @param headB
     * @param headB
     * @return
     */
    private static Node FindFirstCommonNodeByStack(Node headA, Node headB) {
        // 判空
        if (headA == null || headB == null) {
            return null;
        }
        // 初始化
        Stack<Node> stackA = new Stack<>();
        Stack<Node> stackB = new Stack<>();
        // 分别入栈
        while (headA != null) {
            stackA.push(headA);
            headA = headA.next;
        }
        while (headB != null) {
            stackB.push(headB);
            headB = headB.next;
        }
        // 出栈对比
        Node pre = null;
        while (stackA.size() > 0 && stackB.size() > 0) {
            // 栈顶元素相等存入 pre
            if (stackA.peek() == stackB.peek()) {
                pre = stackA.pop();
                stackB.pop();
            } else {
                // 发现不同则跳出
                break;
            }
        }
        return pre;
    }

    /**
     * 法4：拼接两个链表
     * 若存在公共结点，总有 👇
     * 1    2   3   4   5   6   &   11  22  4   5   6
     * 11   22  4   5   6   &   1   2   3   4   5   6
     * 公共结点：4
     *
     * @param headA
     * @param headB
     * @return
     */
    private static Node FindFirstCommonNodeByCombine(Node headA, Node headB) {
        // 判空
        if (headA == null || headB == null) {
            return null;
        }
        // 初始化
        Node p1 = headA;
        Node p2 = headB;
        // 往前走
        while (p1 != p2) {
            // 不同的时候，往前走
            p1 = p1.next;
            p2 = p2.next;
            // 为了防止无公共结点有死循环
            if (p1 != p2) {
                if (p1 == null) {
                    // 链表A走完，拼接B
                    p1 = headB;
                }
                if (p2 == null) {
                    // 链表B走完，拼接A
                    p2 = headA;
                }
            }
        }
        return p1;
    }

    /**
     * 法5：求差值，用快慢指针实现
     *
     * @param headA
     * @param headB
     * @return
     */
    private static Node FindFirstCommonNodeBySub(Node headA, Node headB) {
        // 判空
        if (headA == null || headB == null) {
            return null;
        }
        // 初始化
        Node cur1 = headA;
        Node cur2 = headB;
        // 遍历求长度
        int l1 = 0, l2 = 0;
        while (cur1 != null) {
            cur1 = cur1.next;
            l1++;
        }
        while (cur2 != null) {
            cur2 = cur2.next;
            l2++;
        }
        // 重回头结点
        cur1 = headA;
        cur2 = headB;
        // 差值
        int sub = l1 > l2 ? l1 - l2 : l2 - l1;
        // 长的先走
        if (l1 > l2) {
            int a = 0;
            while (a < sub) {
                cur1 = cur1.next;
                a++;
            }
        }
        if (l2 > l1) {
            int a = 0;
            while (a < sub) {
                cur2 = cur2.next;
                a++;
            }
        }
        // 同步走
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
}
